package com.sort;


import com.zsj.heap.MaxHeap;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/26 17:25
 * @description 堆排序
 */
public class HeapSort {
    /*
    堆可以模拟为一棵完全二叉树
    不是让你写一个完全二叉树 而是模拟出
    我们可以根据某个点的下标计算出它的左右父节点
    假设这个节点的下标是 i
    那么它的左子节点下标是 2*i+1
    右子节点下标是 2*i+2
    父节点下标是 (i-1)/2
    这样我们就可以自己脑补出一个完全二叉树 我们称之为《堆》

    ！堆如何实现
    heapsize 这个是我们当前heap元素的个数 不管数组中有多少个元素 这个heapsize是我们判断堆中元素的基准
    插入元素 我们默认插入到二叉树的末尾 heapsize++ 然后定义一个上浮方法
     上浮方法
         大顶堆:
         我们插入的时候 我们一直判断插入的节点是否大于父节点 如果大于父节点就交换
         重复这个步骤直到没有父节点 或者当前节点比父节点小
         小顶堆:
         很简单 将上面的逻辑反过来就行 不在赘述
   获得元素并且删除:
     很明显 我们返回数组的第一个元素就行
     但是我们需要删除掉这个元素的话 需要下面的步骤
     1、我们需要记录一下这个数组第一个元素 方便后面将他返回
     2、我们将数组的第一个元素和最后一个元素进行交换
     3、将数组的heapsize-1
     4、定义一个下沉方法将交换上来的头部元素下沉下去
        下沉方法:
          大顶堆:
           很明显 下沉的话 我们需要将当前节点去分别与它的左节点和右节点进行比较
           如果小于左节点记录一下左节点的下标 然后在判断右节点 如果右节点大于左节点 就将记录的值更新
           然后判断需要更新的下标有没有变过 如果变了 我们就交换位置
           重复以上步骤 直到交换到没有左右节点 也就是越界了的话就停止
          小顶堆:
           很简单 将上面的逻辑反过来就行 不在赘述
     */
    public static void main(String[] args) {
        int[] n = {5, 6, 3, 9, 7, 8, 5, 1, 2, 4};

        /*
        堆排序的过程中 我们很自然的就将原数组进行了排序
        因为调用了删除并且获得元素的方法
        记得我们每次删除的时候会把最大的元素放到数组的末尾吗
        这就是堆排序
         */
        heapSort(n);
        System.out.println(Arrays.toString(n));
    }

    public static void heapSort(int[] arr) {
        MaxHeap maxHeap = new MaxHeap(arr);
        while (maxHeap.hasNext()) {
            System.out.print(maxHeap.poll() + " ");
        }
    }

    /**
     * 已知一个几乎有序的数组
     * 如果把这个数组排好序的话 每个元素移动的距离可以不超过k
     * 并且k相对数组来说比较小
     * 请选择合适的排序算法进行排序
     */
    public static void sort(int[] arr, int k) {
        /*
        思路：
        使用小顶堆 维护一个k长度的小顶堆
        每次从小顶堆中poll出元素替换到arr[对应的位置]
         */
        //默认是小顶堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        //先往堆中塞入元素 考虑k可能比数组长度大的情况
        int i = 0;
        for (; i < Math.min(k + 1, arr.length); i++) {
            heap.add(arr[i]);
        }
        //继续往堆中添加元素的同时弹出元素 并且设置到对应位置
        int index = 0;
        for (; index < arr.length; index++, i++) {
            heap.add(arr[i]);
            arr[index] = heap.poll();
        }
        //将heap中的元素全部弹出来
        while (!heap.isEmpty()) {
            arr[i++] = heap.poll();
        }
    }
}
